{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Champion II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findChampion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到冠军 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一场比赛中共有 <code>n</code> 支队伍，按从 <code>0</code> 到&nbsp; <code>n - 1</code> 编号。每支队伍也是 <strong>有向无环图（DAG）</strong> 上的一个节点。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> 和一个下标从 <strong>0</strong> 开始、长度为 <code>m</code> 的二维整数数组 <code>edges</code> 表示这个有向无环图，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示图中存在一条从 <code>u<sub>i</sub></code> 队到 <code>v<sub>i</sub></code> 队的有向边。</p>\n",
    "\n",
    "<p>从 <code>a</code> 队到 <code>b</code> 队的有向边意味着 <code>a</code> 队比 <code>b</code> 队 <strong>强</strong> ，也就是 <code>b</code> 队比 <code>a</code> 队 <strong>弱</strong> 。</p>\n",
    "\n",
    "<p>在这场比赛中，如果不存在某支强于 <code>a</code> 队的队伍，则认为 <code>a</code> 队将会是 <strong>冠军</strong> 。</p>\n",
    "\n",
    "<p>如果这场比赛存在 <strong>唯一</strong> 一个冠军，则返回将会成为冠军的队伍。否则，返回<em> </em><code>-1</code><em> 。</em></p>\n",
    "\n",
    "<p><strong>注意</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>环</strong> 是形如 <code>a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>, a<sub>n+1</sub></code> 的一个序列，且满足：节点 <code>a<sub>1</sub></code> 与节点 <code>a<sub>n+1</sub></code> 是同一个节点；节点 <code>a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub></code> 互不相同；对于范围&nbsp;<code>[1, n]</code> 中的每个 <code>i</code> ，均存在一条从节点 <code>a<sub>i</sub></code> 到节点 <code>a<sub>i+1</sub></code> 的有向边。</li>\n",
    "\t<li><strong>有向无环图</strong> 是不存在任何环的有向图。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img height=\"300\" src=\"https://assets.leetcode.com/uploads/2023/10/19/graph-3.png\" width=\"300\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, edges = [[0,1],[1,2]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img height=\"300\" src=\"https://assets.leetcode.com/uploads/2023/10/19/graph-4.png\" width=\"300\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[0,2],[1,3],[1,2]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>m == edges.length</code></li>\n",
    "\t<li><code>0 &lt;= m &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= edge[i][j] &lt;= n - 1</code></li>\n",
    "\t<li><code>edges[i][0] != edges[i][1]</code></li>\n",
    "\t<li>生成的输入满足：如果 <code>a</code> 队比 <code>b</code> 队强，就不存在 <code>b</code> 队比 <code>a</code> 队强</li>\n",
    "\t<li>生成的输入满足：如果 <code>a</code> 队比 <code>b</code> 队强，<code>b</code> 队比 <code>c</code> 队强，那么 <code>a</code> 队比 <code>c</code> 队强</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-champion-ii](https://leetcode.cn/problems/find-champion-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-champion-ii](https://leetcode.cn/problems/find-champion-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[1,2]]', '4\\n[[0,2],[1,3],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        for i in range(N):\n",
    "            flag = 1\n",
    "            for j in range(N):\n",
    "                if grid[i][j] == 1 or i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag == 1:\n",
    "                \n",
    "                return i\n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        for j in range(n):\n",
    "            if sum([grid[i][j] for i in range(n)])==0:\n",
    "                 return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        max_=0\n",
    "        t=0\n",
    "        for i,x in enumerate(grid):\n",
    "            if sum(x)>max_:\n",
    "                max_=sum(x)\n",
    "                t=i\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            if 1 not in col:  # 没有队伍可以击败 j\n",
    "                return j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        buffer = [0]*n\n",
    "        for edge in edges:\n",
    "            in_node = edge[1]\n",
    "            buffer[in_node] += 1\n",
    "        \n",
    "        out_nodes = list()\n",
    "        for i in range(n):\n",
    "            if buffer[i] ==0:\n",
    "                out_nodes.append(i)\n",
    "        if len(out_nodes)>1:\n",
    "            return -1\n",
    "        else:\n",
    "            return out_nodes[0]\n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, n: int, edges: List[List[int]]) -> int:\n",
    "        weak = [False] * n\n",
    "        for x, y in edges:\n",
    "            weak[y] = True\n",
    "        ans = -1\n",
    "        for num in range(n):\n",
    "            if not weak[num]:\n",
    "                if ans != -1:\n",
    "                    return -1\n",
    "                ans = num\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = set([i for i in range(n)])\n",
    "        for edge in edges:\n",
    "            if edge[1] in ans:\n",
    "                ans.remove(edge[1])\n",
    "        if len(ans) > 1:\n",
    "            return -1\n",
    "        for a in ans:\n",
    "            return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = [0] * n\n",
    "        for _, b in edges:\n",
    "            d[b] += 1\n",
    "        \n",
    "        champion = -1\n",
    "        for i, s in enumerate(d):\n",
    "            if s == 0:\n",
    "                if champion == -1:\n",
    "                    champion = i\n",
    "                else:\n",
    "                    champion = -1\n",
    "                    break\n",
    "        return champion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, n: int, e: List[List[int]]) -> int:\n",
    "        d=[0]*n\n",
    "        for i,j in e:\n",
    "            d[j]+=1\n",
    "        ans=[i for i in range(n) if d[i]==0]\n",
    "        return ans[0] if len(ans)==1 else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
